Sometimes the object module produced by a compiler includes information (from the symbol table) mapping all source program names to their addresses. The most likely purpose of this information is,for use as input to a debugging aid,to increase the run-time efficiency of the program,for the reduction of the symbol-table space needed by the compiler,to tell the loader where each variable belongs,A
"Suppose there is an open (external) hash table with four buckets, numbered 0,1,2,3, and integers are hashed into these buckets using hash function h(x) = x mod 4. If the sequence of perfect squares 1,4,9, ... , i^2, ... is hashed into the table, then, as the total number of entries in the table grows, what will happen?","Two of the buckets will each get approximately half the entries, and the other two will remain empty.",All buckets will receive approximately the same number of entries.,All entries will go into one particular bucket.,"All buckets will receive entries, but the difference between the buckets with smallest and largest number of entries will grow.",A
"Of the following page-replacement policies, which is guaranteed to incur the minimum number of page faults?",Replace the page whose next reference will be the longest time in the future.,Replace the page whose next reference will be the shortest time in the future.,Replace the page whose most recent reference was the shortest time in the past.,Replace the page whose most recent reference was the longest time in the past.,A
Let f(X) = if x = 1 then 0 else [x * f(x - 1) + x**2]. The value of f(4) is,53,29,50,100,D
"Church's thesis equates the concept of ""computable function"" with those functions computable by, for example, Turing machines. Which of the following is true of Church's thesis?",It was first proven by Alan Turing.,"It has not yet been proven, but finding a proof is a subject of active research.",It can never be proven.,It is now in doubt because of the advent of parallel computers.,C
Which of the following statements is FALSE about memory reclamation based on reference counting?,Reference counting is well suited for reclaiming cyclic structures.,Reference counting incurs additional space overhead for each memory cell.,Reference counting is an alternative to mark-and-sweep garbage collection.,Reference counting need not keep track of which cells point to other cells.,A
"Suppose it takes 1 second to factor a general 100 x 100 matrix using Gaussian elimination. Of the following, which is the best estimate of the number of seconds it will take to factor a 500 x 500 matrix based on the relative dimensions?",5,10,25,125,D
The main difference between a network operating system and a distributed operating system is that,"A network operating system hides the existence of many machines from the user, but a distributed operating system makes the existence of many machines visible","A distributed operating system hides the existence of many machines from the user, but a network operating system makes the existence of many machines visible","A network operating system uses a local-area network, while a distributed operating system uses a wide-area network","A distributed operating system uses a local-area network, while a network operating system uses a wide-area network",B
"If L is a language accepted by some automaton M, which of the following is (are) true?
I. If M is a nondeterministic finite automaton, then L is accepted by some deterministic finite automaton.
II. If M is a deterministic pushdown automaton, then L is accepted by some nondeterministic pushdown automaton.
III. If M is a nondeterministic pushdown automaton, then L is accepted by some deterministic Turing machine.",III only,I and II only,II and III only,"I, II, and III",D
"Consider the following possible data structures for a set of n distinct integers.
I. A min-heap
II. An array of length n sorted in increasing order
III. A balanced binary search tree
For which of these data structures is the number of steps needed to find and remove the 7th largest element O(log n) in the worst case?",I only,II only,I and II,II and III,D
"Which of the following evaluation strategies must be defined in order to execute a logic program on a sequential machine?
I. Evaluation order of rules
II. Evaluation order of clauses
III. Evaluation order of arguments in each clause",II only,I and II only,I and III only,"I, II, and III",D
